

//
//  BinarySearchTree.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/20.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 二叉搜索树
public class BinarySearchTree<Element: Comparable>: BinaryTree<Element> {
        
    /// search接口所命中节点的父亲
    var _hot: Node<Element>?
    
    @discardableResult
    public func insert(_ element: Element) -> Node<Element> {
        var node = search(element)
        if node == nil { // 禁止了雷同元素 因此只在查找失败时才插入
            if let hot = _hot {
                _size += 1
                if element < hot.value {
                    node = hot.insertAsLC(element)
                } else {
                    node = hot.insertAsRC(element)
                }
                updateHeightAbove(node)
            } else {
                _size += 1
                _root = Node(element)
                node = _root
            }
        }
        return node!
    }
    
    
    @discardableResult
    public func remove(_ element: Element) -> Bool {
        guard let node = search(element) else { return false }
        remove(at: node, hot: &_hot)
        _size -= 1
        updateHeightAbove(_hot)
        return true
    }
}
